package src.算法.快速排序;

public class FastSort {

    // 对数组内的元素排序
    public static void sort(Comparable[] a){
       int lo = 0;
       int hi = a.length-1;
       sort(a,lo,hi);
    }

    // 对数组内指定部分元素排序
    private static void sort(Comparable[] a,int lo,int hi){
        // 安全性校验
        if(lo>=hi){
            return;
        }
        // 1.对lo到hi之间的元素进行分组【左右子组】
        int s_index = splitIndex(a, lo, hi); // 位置变化后的索引
        // 左子组排序
        sort(a, lo, s_index-1);
        // 右子组排序
        sort(a, s_index+1 ,hi);
    }

    // 在数组中，从索引lo到索引hi之间的元素进行分组，并返回分组界线的索引
    public static int splitIndex(Comparable[] a,int lo,int hi){
        // 确定分界值
        Comparable key = a[lo];
        // 定义两个指针，指向最小索引处和最大索引处的下一个值
        int left = lo;
        int right = hi+1;
        // 切分
        while (true){
            // 先从左往右扫描，移动right指针，找到一个比分界值小的元素，停止
            while (less(key,a[--right])){ // --right直接找到最后一个元素
                if(right==lo){
                    break;
                }
            }
            // 再从右往左扫描，移动left指针，找到一个比分界值大的元素，停止
            while (less(a[++left],key)){ // ++right找到数组第二个元素
                if(left==hi){
                    break;
                }
            }
            // left<right交换元素
            if(left>=right){
                break;
            }else {
                exch(a,right,left);
            }
        }
        exch(a,lo,right); // 交换分界值
        return right;
    }

    // 比较前一个元素是否小于后一个元素
    private static boolean less(Comparable a,Comparable b){
        int result = a.compareTo(b);
        return result<0;
    }
    // 数组元素i和j交换位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
